package 力扣.并查集;

public class 省份数量547 {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        Init(n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j){
                    if (isConnected[i][j] == 1){
                        Union(i, j);
                    }
                }
            }
        }
        return count;
    }
    private int[] F;
    private int count;
    private void Init(int n){
        F = new int[n];
        for (int i = 0; i < n; i++) {
            F[i] = i;
        }
        count = n;
    }
    private int Find(int x){
        if (x == F[x]){
            return x;
        }
        return F[x] = Find(F[x]);
    }
    private void Union(int x,int y){
        if (Find(x) != Find(y)){
            count--;
            F[Find(x)] = Find(y);
        }
    }



}
